A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Redukcia v zmysle teórie vypočítateľnosti je vyjadrenie problému v podobe inštancie iného problému. Pomocou redukcie sa definujú triedy zložitosti. Ak sa dá problém A redukovať na problém B, a B sa dá redukovať na A, hovoríme, že A a B sú rovnako ťažké problémy, alebo že A aj B patria do rovnakej triedy zložitosti.
Ako funguje redukcia problému A na problém B? Je to taký postup, ktorý:
- transformuje vstup problému A na vstup problému B
- vyrieši B
- transformuje výstup B na výstup A
Príklad:
Majme čiernu skrinku B, ktorá vie vypočítať funkciu sínus. Chceme vedieť počítať problém A, ktorý pre dané vráti súčin .
Na to môžeme využiť vzorec . Treba len vhodne transformovať vstupy a výstupy. Rovnica sa dá upraviť na . Takže naša redukcia bude vyzerať takto:
- zoberieme vstup , transformujeme ho na
- vyriešime B so vstupom , výsledok bude
- tento výsledok vydelíme dvoma, čo je výsledok A
Tento príklad je len ilustračný, redukcia sa využíva hlavne v prípadoch, keď je náročné reprodukovať riešenie problému B, alebo sme na to leniví. Využijeme len to, že B vieme riešiť. Napríklad na kalkulačke máme tlačidlo sin, ktorý počíta sínus, ale málokoho zaujíma, ako vnútorne funguje. Vyššie uvedený príklad sa dá využiť v prípade, keď sa nám pokazí tlačidlo kosínus.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
AOL Instant Messenger
Apache OpenOffice
Bioinformatika
Build
Cardware
Datagram
Diagram prípadov použitia
Digitálne pero
Django (framework)
Django Framework
EBCDI
Emule
Entita (informatika)
Exabajt
Exbibajt
Fake mailer
Funkcionálne programovanie
Gibibajt
Gigabajt
GNU Lesser General Public License
Graphics Device Interface
H.264/MPEG-4 AVC
Hyperlink
Informatika
Interpreter
Interpreter (programovanie)
Jakarta EE
Java applet
Java ME
Jingle
Kaspersky Anti-Virus
Kibibajt
Kilobajt
Kliknutie
Kompilácia (programovanie)
Kompresný pomer (informatika)
Kontrolný súčet
Lambda kalkul
LibreOffice Writer
LogMeIn Hamachi
Manažment služieb IT
McAfee VirusScan
Mebibajt
Megabajt
Mozilla Corporation
Mozilla Thunderbird
Musical Instrument Digital Interface
NP-úplný problém
Objektovo orientované programovanie
OLAP kocka
OpenID
Pažravý algoritmus
Pebibajt
Petabajt
Polynomiálna transformovateľnosť
Portable Network Graphics
Printer Command Language
Programovanie (informatika)
Program Information File
Redukcia (teoretická informatika)
RGBA
Súbor dát
Spúšťateľný program
Stavový diagram UML
Subpixel
Syntaktická analýza
Tebibajt
Terabajt
Token (text)
Total Commander
TrueSpace
Very High Speed Digital Subscriber Line 2
Virtual Console
Virus Bulletin
Vuze
Weighted RED
Windows Live Messenger
XM
Yobibajt
Yottabajt
Zabezpečený hypertextový prenosový protokol
Zebibajt
Zettabajt
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk